package LeetCode1;

import java.util.LinkedList;
import java.util.Queue;

//二叉树的完整性检测
public class Num958 {
    //状态转换，一种节点是有子树的节点，一种是叶子节点,所以需要布尔常量来进行转换
    //其中有子节点的节点中，最后一个节点有两种，一种是只有左子树，一种是都有
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isFather = true;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (isFather) {
                if (cur.left != null && cur.right != null) {
                    //如果都不为空，则入队两个子节点
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                } else if (cur.left != null) {
                    //此时说明右子树为空，则此节点是最后一个父节点，下一节点为子节点，状态转换
                    isFather = false;
                    queue.offer(cur.left);
                } else if (cur.right != null) {
                    //此时说明左子树为空，右子树不为空，则直接不符合完全二叉树
                    return false;
                } else {
                    //左右子树都为空，说明该节点为子节点，状态转换
                    isFather = false;
                }
            } else {
                // 此时处在第二状态,所有节点都必须是叶子节点，找到一个反例就不是完全二叉树
                if (cur.left != null || cur.right != null) {
                    return false;
                }
            }
        }
        return true;
    }
}
